#ifndef _H_DIG_RBTREE_H_
#define	_H_DIG_RBTREE_H_

#include <stdarg.h>
#include <stdint.h>
#include <string.h>

#include "dig_mem_pool.h"
#include "dig_wire_name.h"
#include "dig_buffer.h"

/*
 * Each node store one domain name and the data identified by the name
 * The node used to maintain the hierarchy of domain space and the down pointer 
 * points to the subtree of subdomains.
 * 
 * The current design will ensure that domain name in same level tree will
 * have same label count and same ancestor. 
 *
 * One kind of node is special which is created automatically when it's child is 
 * inserted into the rbtree instead of itself, in this case, this node is called 
 * non-terminal its data is always NULL
 *
 * name_rbnode will be used by name_rbtree internally, so the interface is 
 * quite limited 
 * */
typedef struct domain_rbnode domain_rbnode_t;
const wire_name_t *     domain_rbnode_get_name(const domain_rbnode_t *node);

//next node which is bigger than node in the same tree
const domain_rbnode_t * domain_rbnode_successor(const domain_rbnode_t *node);
const domain_rbnode_t * domain_rbnode_predecessor(const domain_rbnode_t *node);

void                    domain_rbnode_set_callback(domain_rbnode_t *node, bool needs_call);
bool                    domain_rbnode_needs_callback(const domain_rbnode_t *node);
bool                    domain_rbnode_has_child(const domain_rbnode_t *node);

void                    domain_rbnode_set_data(domain_rbnode_t *node, const void *data);
const void*             domain_rbnode_get_data(const domain_rbnode_t *node);

void                    domain_rbnode_set_locknum(domain_rbnode_t *node, uint8_t locknum);
uint8_t                 domain_rbnode_get_locknum(const domain_rbnode_t *node);

//Add reference to the node to avoid it been deleted by others
void                    domain_rbnode_retain(domain_rbnode_t *node);
//When done with this node, remove the reference to the node, then the node can be freed
bool                    domain_rbnode_release(domain_rbnode_t *node);
//Get how many references to this node
int                     domain_rbnode_get_reference_count(const domain_rbnode_t *node);


/*
 *  null node is one special node which has same meaning with NULL, but
 *  instead of use NULL but a special kind of node is a design decision.
 *  Empty node is the node without data, it's not a null node, in most case
 *  empty node is non-terminal
 * */
bool                    domain_rbnode_is_null(const domain_rbnode_t *node);
bool                    domain_rbnode_is_empty(const domain_rbnode_t *node);


/*
 * node chain used to store all the node along the path from root to the 
 * destional node
 * */
typedef struct domain_rbnode_chain domain_rbnode_chain_t;
domain_rbnode_chain_t * domain_chain_create();
domain_rbnode_chain_t * domain_chain_copy(domain_rbnode_chain_t *path);
void domain_chain_delete(domain_rbnode_chain_t *path);

/*
 * node chain is filled during rbtree find, so there is no push interface
 * */
uint32_t domain_chain_get_node_count(const domain_rbnode_chain_t *chain);
const domain_rbnode_t *domain_chain_top(const domain_rbnode_chain_t *path);
void domain_chain_pop(domain_rbnode_chain_t *path);

/*
 * remove the node from the node path, which will release the node reference
 * note: when done with node chain, it should be deleted or cleared
 * otherwise the nodes in it will be reference which will cause memory leak
 * */
void domain_chain_clear(domain_rbnode_chain_t *path);

/*
 * BTree is a generic map from domain name to any kind of data. Internally,
 * it uses a red-black tree. However, it isn't one tree containing everything.
 * Subdomains are trees, so this structure is recursive - trees inside trees.
 * But, from the interface point of view, it is opaque data structure
 *
 * with the following name:
 * a
 * b
 * c
 * x.d.e.f
 * z.d.e.f
 * g.h
 * o.w.y.d.e.f
 * p.w.y.d.e.f
 * q.w.y.d.e.f
 *
 * the final tree will look like:
 *                                  .
 *                                  |
 *                                  b
 *                                 / \
 *                                a   f
 *                                  / | \
 *                                 c  |  h
 *                                   e.f |
 *                                    |  g.h
 *                                  d.e.f
 *                                    |
 *                                 y.d.e.f
 *                               /    |    \
 *                              /     |     \
 *                            x.d.e.f |    z.d.e.f
 *                                w.y.d.e.f
 *                                    |
 *                               p.w.y.d.e.f
 *                                /        \
 *                          o.w.y.d.e.f    q.w.y.d.e.f
 *
 *
 *
 *
 *
*/                 
typedef struct domain_rbtree domain_rbtree_t;
typedef enum domain_rbtree_find_result
{
      EXACTMATCH = 0,
      PARTIALMATCH, 
      NOTFOUND,   
      FIND_INTERRUPT_BY_CALL_BACK,
      SEVER_FAILED
}domain_rbtree_find_result_t;

typedef void(*domain_rbtree_value_deleter_t)(void *data);
//note : deleter is the funciton to free the value part of the domain tree,
//it shouldn't NULL, in that case it means the data doesn't needs free.
domain_rbtree_t *domain_rbtree_create(const wire_name_t *root_name, domain_rbtree_value_deleter_t deleter);
void domain_rbtree_delete(domain_rbtree_t *rbtree);
uint32_t domain_rbtree_get_node_count(const domain_rbtree_t *tree);


//Root node is the node with the tree creation, simply put there is no tree without a root node
//So during the tree modification(insert, delete), the root node won't change.
//Root node will be deleted only when the tree is deleted.
domain_rbnode_t *domain_rbtree_get_root_node(domain_rbtree_t *tree);

// Set whether return non-terminal node during find
// the policy will affect find, next_node, prev_node, first_node and last_node
void domain_rbtree_set_return_nonterminal(domain_rbtree_t *tree, bool does_return_nonterminal);

// During the search in name rbtree, if one node is set needs callback, 
// the callback function will be invoked, if this function returns false,
// the search process will be interrupted, otherwise the normal search process 
// will continue after the call back funciton.
// whether non-terminal is returned based on search policy setted, by default
// it won't returned
typedef bool (*domain_rbnode_callback_t)(const domain_rbnode_t *node, void *parameter);
domain_rbtree_find_result_t domain_rbtree_find(const domain_rbtree_t *tree,
                                               const wire_name_t *name,
                                               domain_rbnode_t ** node,
                                               domain_rbnode_chain_t *node_path,
                                               domain_rbnode_callback_t callback,
                                               void *callback_arg);

/*
 *  Difference between find & continue_find is that node_path in find must be empty
 *  but in continue_find, node_path is the result of previous find or continue_find
 *  this function utilize the last find result, to accelerate finding process.
 *  note: the target name should be sub domain of the top domain in node path.
 * */
domain_rbtree_find_result_t domain_rbtree_continue_find(const domain_rbtree_t *tree,
                                                        const wire_name_t *name,
                                                        domain_rbnode_t ** node,
                                                        domain_rbnode_chain_t *node_path,
                                                        domain_rbnode_callback_t callback,
                                                        void *callback_arg);


domain_rbtree_find_result_t domain_rbtree_simple_find(const domain_rbtree_t *tree,
                                                    const wire_name_t *name,
                                                    domain_rbnode_t **node);


//find the next name which is bigger than the top node of node path
//return false if the name of the node path's top node is the biggest name
//otherwise return true
//if return true, next node will point to the next node and node path
//will save the path to the next node from the zone apex, this find also
//affected by return non-terminal policy
//note: node path should save the complete path from zone apex to the 
//to top node of node path
bool domain_rbtree_next_node(const domain_rbtree_t *tree, 
                             domain_rbnode_chain_t *node_path,
                             const domain_rbnode_t **next_node);

bool domain_rbtree_prev_node(const domain_rbtree_t *tree, 
                             domain_rbnode_chain_t *node_path,
                             const domain_rbnode_t **next_node);

//make first node point to the first node of the tree 
//this function can be used as the start point to iterate the whole tree
//using domain_rbtree_next_node
//node_path will store all the nodes from root to first_node,
//if node_path isn't empty at the begining, it will be clear first
bool domain_rbtree_first_node(const domain_rbtree_t *tree, 
                              domain_rbnode_chain_t *node_path,
                              const domain_rbnode_t **first_node);

//last_node will point to the biggest name in the tree
//node_path will store all the nodes from root to last_node
//if node_path isn't empty at the begining, it will be clear first
bool domain_rbtree_last_node(const domain_rbtree_t *tree, 
                             domain_rbnode_chain_t *node_path,
                             const domain_rbnode_t **last_node);

// If the name doesn't exist, new node will be created and returned
// otherwise the already exists one will be returned, if there is no memory
// to create new node, null node(NOT NULL) will return
// If the name's ancestors don't exist in current tree, they will be inserted
// automatically, this kind of node is called non-terminal, and the non-terminal 
// node callback will be called
typedef void (*domain_non_terminal_rbnode_create_callback_t)(domain_rbnode_t *node, void *parameter);
domain_rbnode_t *domain_rbtree_insert_domain(domain_rbtree_t *tree, 
                                             const wire_name_t *name,
                                             domain_non_terminal_rbnode_create_callback_t callback,
                                             void *parametr);


// If no node with the name in the tree, false will be returned, otherwise true will be return.
// If the name is a leaf node, the node will be deleted
// If the domain has subdomains, the node will still be here but its data will be deleted
// Once one leaf node is deleted, all its non-terminal ancestor will be delete too. 
// Althought empty node is 100 percent non-terminal, 
// it cann't be sure that non-empty node is not non-terminal node, so we add
// callback function to check whether the node is non-terminal for non-empty node
// note: the root node of the tree can't be deleted. Delete the root node just make it's data be empty
// even it is the only node in the tree
typedef bool(*domain_rbnode_is_non_terminal_callback_t)(const domain_rbnode_t *node, void *parameter);
bool domain_rbtree_delete_domain(domain_rbtree_t *tree, 
                                 const wire_name_t *name,
                                 const domain_rbnode_t **undel_parent_node,
                                 domain_rbnode_is_non_terminal_callback_t callback,
                                 void *parameter);


uint32_t domain_rbtree_to_text(const domain_rbtree_t *tree, buffer_t *buf);

#endif 
